package com.example.hashtable18.hash;

/**
 * @description 散列表实现
 * @auther lijiewei
 * @date 2021/9/9 20:20
 */
public class HashTable<K, V> {

    /** 散列表默认长度. */
    private static final int DEFAULT_INITAL_CAPACITY = 8;
    /** 装载因子. */
    private static final float LOAD_FACTOR = 0.75f;
    /** 初始化散列表数组. */
    private Entry<K, V>[] table;
    /** 实际元素数量. */
    private int size = 0;
    /** 散列表索引数量. */
    private int use = 0;

    public HashTable() {
        table = (Entry<K, V>[]) new Entry[DEFAULT_INITAL_CAPACITY];
    }

    /**
     * 新增
     * @param key 键
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/9/9 20:29
     */
    public void put(K key, V value) {
        int index = hash(key);
        //位置未被引用，创建哨兵结点
        if (table[index] == null) {
            table[index] = new Entry<>(null, null, null);
        }
        //取出table[index]的哨兵结点，在哨兵结点后增加结点
        Entry<K, V> tmp = table[index];
        //只有哨兵结点，没有形成链（删除导致的）
        if (tmp.getNext() == null) {
            tmp.setNext(new Entry<>(key, value, null));
            size++;
            use++;
            //动态扩容
            if (use >= table.length*LOAD_FACTOR) {
                resize();
            }
        } else {
            //有后续的链
            while (tmp.getNext() != null) {
                tmp = tmp.getNext();
                if (tmp.getKey() == key) {
                    tmp.setValue(value);
                    return;
                }
            }
            Entry<K, V> curNode = new Entry<>(key, value, table[index].getNext());
            table[index].setNext(curNode);
            size++;
        }
    }

    /**
     * 扩容
     * @return
     * @author lijiewei
     * @date   2021/9/10 11:26
     */
    private void resize() {
        Entry<K, V>[] oldTable = table;
        table = (Entry<K, V>[]) new Entry[(table.length * 2)];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] == null || oldTable[i].getNext() == null) {
                continue;
            }
            Entry<K, V> tmp = oldTable[i];
            while (tmp.getNext() != null) {
                tmp = tmp.getNext();
                int index = hash(tmp.getKey());
                if (table[index] == null) {
                    //创建哨兵结点
                    table[index] = new Entry<>(null, null, null);
                    use++;
                }
                table[index].setNext(new Entry<>(tmp.getKey(), tmp.getValue(), table[index].getNext()));
            }
        }
    }

    /**
     * 获取
     * @param key 键
     * @return
     * @author lijiewei
     * @date   2021/9/10 11:39
     */
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> tmp = table[index];
        if (tmp == null || tmp.getNext() == null) {
            return null;
        }
        while(tmp.getNext() != null) {
            tmp = tmp.getNext();
            if (tmp.getKey() == key) {
                return tmp.getValue();
            }
        }
        return null;
    }

    /**
     * 删除
     * @param key 键
     * @return
     * @author lijiewei
     * @date   2021/9/10 13:56
     */
    public void remove(K key) {
        int index = hash(key);
        Entry<K, V> tmp = table[index];
        if (tmp == null || tmp.getNext() == null) {
            return;
        }
        while(tmp.getNext() != null) {
            if (key == tmp.getNext().getKey()) {
                tmp.setNext(tmp.getNext().getNext());
                size--;
                if (table[index].getNext() == null) {
                    use--;
                }
                return;
            }
            tmp = tmp.getNext();
        }
    }

    /**
     * 散列函数
     * @param key
     * @return
     * @author lijiewei
     * @date   2021/9/10 9:27
     */
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;
    }


}
